#include <iostream>
using namespace std;


struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
		val(x), next(NULL) {
	}
};

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
	if (pHead1 == NULL && pHead2 != NULL)
		return pHead2;
	if (pHead1 != NULL && pHead2 == NULL)
		return pHead1;
	if (pHead1 == NULL && pHead2 == NULL)
		return NULL;
	ListNode* pre = pHead1;
	if (pHead1->val > pHead2->val)
	{
		pHead1 = pHead2;
		pHead2 = pre;
		pre = pHead1;
	}
	ListNode* p = pre->next;
	while (pHead2 != NULL)
	{
		while (p != NULL && p->val < pHead2->val)
		{
			p = p->next;
			pre = pre->next;
		}
		ListNode* insertNode = pHead2;
		pHead2 = pHead2->next;
		insertNode->next = p;
		pre->next = insertNode;
		pre = pre->next;
	}
	return pHead1;
}



//int main()
//{
//	ListNode* head = new ListNode(1);
//	ListNode* p1 = head;
//	ListNode* head2 = new ListNode(2);
//	ListNode* p2 = head2;
//	for (int i = 2; i < 11; ++i)
//	{
//		ListNode* p = new ListNode(i);
//		if (i % 2)
//		{
//			p1->next = p;
//			p1 = p1->next;
//		}
//		else
//		{
//			p2->next = p;
//			p2 = p2->next;
//		}
//		
//	}
//
//	Merge(head, head2);
//
//	system("pause");
//	return 0;
//}